今天是動態規劃的最後一天，整理幾題比較複雜的動態規劃題目，當作前面幾天內容的總結~~直接進例題

例題實戰

[887.雞蛋掉落]（https://leetcode-cn.com/problems/super-egg-drop/）
思路：
一個雞蛋從k層樓丟下去，只有碎與沒碎兩種可能
如果有dp[i][j]表示i顆雞蛋，j層樓的最少次數，可得：
dp[i][j] = max(dp[i][j-t],dp[i-1][t-1]+1)~>將蛋丟在t樓

程式碼實現：

[法一] 2Ddp

dp[i][j]表示在有i顆蛋、k層樓的情況下，需要執行的最小次數
則可得 {dp[i][j] = max(dp[i][j-t],dp[i-1][t-1]+1)}~>將蛋丟在t樓
dp[i][j]狀態可由dp[i][j-t]->沒破，問題簡化至i顆蛋，j-t樓，dp[i-1][t-1]->蛋破了，問題簡化成i-1顆蛋，t-1樓
而一顆蛋丟下去只有兩種狀態(破與沒破且都要考慮)故dp[i][j]狀態可由這兩種狀態演進而成
由狀態轉移方程發現在考慮dp[i][j]時，[1~j]都要丟蛋，使得時間複雜度O(KN^2)

[法二] 二分搜尋優化

在變數t的線性搜尋中發現dp[i][j-t]遞減的最小值dp[i][0] = 0, dp[i-1][t-1]遞增的最大值dp[i-1][j-1]，得兩函數在[1~N]有交點
並且兩函數會有有序的遞增、遞減關係，以此用二分搜尋代替線性搜尋

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
        for(int i = 1; i<=k; i++){ 
            for(int j = 1; j<=n; j++){ 
                if(i==1){
                    dp[i][j] = j;
                }
                else{
                    int mmin = INT_MAX;
                    //丟第t層
                    //此處有兩種寫法(1.線性搜索-->超時 2. 二分搜尋)

                    //1.
                    // for(int t = 1; t<=j; t++){
                    //     int v = max(dp[i][j-t],dp[i-1][t-1])+1;
                    //     mmin = min(v, mmin);
                    // }
                    // dp[i][j] = mmin;

                    // 2.
                    int f = 1, b = j;
                    int mid = -1;
                    while(b>=f){
                        mid = f+(b-f)/2;
                        if(dp[i][j-mid]==dp[i-1][mid-1]){
                            mmin = min(mmin, dp[i-1][mid-1]+1);
                            break;
                        }
                        else if(dp[i-1][mid-1] > dp[i][j-mid]){
                            b = mid-1;
                            mmin = min(mmin, dp[i-1][mid-1]+1);
                        }
                        else if(dp[i-1][mid-1] < dp[i][j-mid]){
                            f = mid+1;
                            mmin = min(mmin, dp[i][j-mid]+1);
                        }                        
                    }
                    dp[i][j] = mmin;
                }
            }
        }
        // for(int i = 1; i<dp.size(); i++){
        //     for(int j = 1; j<dp[0].size(); j++){
        //         cout<< dp[i][j]<<" ";
        //     }
        //     cout<< endl;
        // }
        return dp[k][n];
    }
};

10. 正则表达式匹配
思路:
用dp[i][j]s前 i 個字元是否與 p 中的前 j 個字元匹配
則可得：
一般狀況:
dp[i][j] = dp[i-1][j-1] {s[i]=p[j] or p[j-1] == '.'}
遇到*:
dp[i][j] = dp[i-1][j]|dp[i][j-1]|dp[i][j-2]

class Solution {
public:
    bool isMatch(string s, string p) {
        //dp[i][j]為s[1]~str[i]和 p[1]~p[j]
        if (p.empty()) return s.empty();
        vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1, 0)); dp[0][0] = 1;
        // 初始化dp[0][j]表示p[1:j]與空串的匹配情况
        for (int j = 1; j <= p.size(); j++) {
            if (p[j-1] != '*') continue;
            else dp[0][j] = dp[0][j-2];
        }
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= p.size(); j++) {
                if (s[i-1] == p[j-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1]; //一般匹配
                else if (p[j-1] == '*') {  //遇到*時的處理
                    dp[i][j] = dp[i][j-2]; //把*當0次
                    if (p[j-2] == '.' || p[j-2] == s[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

329. 矩阵中的最长递增路径
思路：利用空間來記錄每一個起點開始的最大路徑

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int M = matrix.size(); 
        int N = matrix[0].size(); //matrix不為空
        vector<vector<int> > dp(M, vector<int>(N, -1)); //-1表示未搜索過
        int res = 0;
        int tmp = 0;
        for(int i = 0; i<M; ++i){
            for(int j = 0; j<N; ++j){
                tmp = dfs(matrix, dp, i ,j);
                res = max(res, tmp);
                //cout<< tmp<<" ";
            }
            //cout<< endl;
        }
        return res;
    }
    //fill dp matrix
    int dfs(vector<vector<int> >& matrix, vector<vector<int> >& dp, int x, int y){
        if(dp[x][y]!=-1){
            return dp[x][y];
        }
        int res = 1;
        int M = matrix.size(); 
        int N = matrix[0].size(); //matrix不為空
        int travel_lr[] = {1,0,-1,0};
        int travel_td[] = {0,1,0,-1};
        for(int i = 0; i<4; ++i){
            if(x+travel_lr[i]>=M || x+travel_lr[i]<0 || y+travel_td[i]>=N || y+travel_td[i]<0){
                continue;
            }
            if(matrix[x+travel_lr[i]][y+travel_td[i]] < matrix[x][y]){
                res = max(res, dfs(matrix, dp, x+travel_lr[i], y+travel_td[i])+1);
            }
        }
        return dp[x][y] = res;
    }
};